package com.buddy.learn.algorithm.exam;

import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * @author Buddy
 * @date 2021/5/20
 */
public class Solution2 {

    private static TNode init() {
        // 必须逆序建立，因为上面的节点会用到下面的子节点
        TNode N = new TNode(7, null, null);
        TNode H = new TNode(6, null, null);
        TNode E = new TNode(5, H, N);
        TNode D = new TNode(4, null, null);
        TNode C = new TNode(3, null, null);
        TNode B = new TNode(2, D, E);
        TNode A = new TNode(1, B, C);
        return A;
    }

    public static void main(String[] args) {
        TNode root = init();
        System.out.println(getDeep(root));
    }

    private static int getDeep(TNode root) {
        if (null == root) {
            return 0;
        }
//        Stack<TNode> cache = new Stack<>();
        Queue<TNode> cache = new LinkedBlockingQueue<>();
        System.out.println(root.data);
        while (root.left != null || root.right != null) {
            if (root.left != null) {
                cache.add(root.left);
            }
            if (root.right != null) {
                cache.add(root.right);
            }
            root = cache.poll();
            System.out.println(root.data);
        }
        while (!cache.isEmpty()) {
            root = cache.poll();
            System.out.println(root.data);
        }
        return 0;
    }

    private static class TNode {
        TNode left;
        TNode right;
        int data;

        public TNode(int data, TNode left, TNode right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }
}
